Media clips or media content are segments of audio media, video media, or audio/visual (AV) media and include information that is embodied, stored, transmitted, received, processed, or otherwise used with at least one medium. Common media clip formats include FLV format (flash video), Windows Media Video, RealMedia, Quicktime, MPEG, MP3, and DivX. As used herein, the terms “media clips”, “media content,” “information content,” and “content” may be used interchangeably.
Media clips may be defined with one or more images. For example, video media may be a combination of a set of temporally related frames or images at particular points in time of the video media. Additionally, audio media may be represented as one or more images using many different techniques known in the art. For example, audio information may be captured in a spectrogram. In the spectrogram, the horizontal axis can represent time, the vertical axis can represent frequency, and the amplitude of a particular frequency at a particular time can be represented in a third dimension. Further, in a two dimensional spectrogram, the amplitude may be represented with thicker lines, more intense colors or grey values. Those skilled in the art will appreciate that many different modifications to the above example and other representations may be used to represent an audio clip as an image.
Images that define media content (audio and/or video) may be associated with a corresponding fingerprint (“fingerprint” used interchangeably with and equivalent to “signature”). Some fingerprints of media content may be derived (e.g., extracted, generated) from information within, or which comprises a part of the media content. A media fingerprint embodies or captures an essence of the media content of the corresponding media and may be uniquely identified therewith. Video fingerprints are media fingerprints that may be derived from images or frames of a video clip. Audio fingerprints are media fingerprints that may be derived from images with embedded audio information (e.g., spectrograms). Further, the term media fingerprint may refer to a low bit rate representation of the media content with which they are associated and from which they are derived.
Most applications of content identification using media fingerprints rely on a large database of media fingerprints. Any query fingerprint that is extracted from query media is compared against this database of media fingerprints to identify matches. As the size of database increases in terms of number of hours of media, it is desirable that the uniqueness of fingerprint codewords is not reduced. A fingerprint codeword generally represents a sequence of fingerprint bits that is used for indexing (e.g., in a hash table) the media fingerprints. The fewer number of fingerprints/media files that correspond to a fingerprint codeword, the more unique the fingerprint codeword is. This uniqueness property of the fingerprint codewords allows for scaling of the fingerprint database to a large number of hours. However, if certain fingerprint codewords are more likely to occur than others, then as the database size grows the uniqueness reduces since the more likely fingerprint codewords will each link to a large number of fingerprints/media files. The large number of fingerprints/media files corresponding to fingerprint codewords results in more computations to perform content identification. For example, in a hash-table based searching method a fingerprint codeword of a query fingerprint may be used to identify all fingerprints/media files in a fingerprint database that are linked to the same fingerprint codeword. Multiple fingerprints/media files being linked to the same fingerprint codeword is referred to as collisions. The larger the number of collisions (i.e., fingerprints/media files) for the same fingerprint codeword, the greater the computations required to determine which one of the fingerprints/media files corresponding to the fingerprint codeword are equivalent or the best match to the query fingerprint. The fewer the number of collisions (i.e., fingerprints/media files) for the same fingerprint codeword, the lesser the computations required to determine which one of the fingerprints/media files corresponding to the fingerprint codeword are equivalent or the best match to the query fingerprint. Thus, the fingerprints that have a small number of average collisions per fingerprint codeword will result in shorter search duration. Such fingerprints are scalable for searching through a larger database of fingerprints than fingerprints for which the average number of collisions is higher.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section. Similarly, issues identified with respect to one or more approaches should not assume to have been recognized in any prior art on the basis of this section, unless otherwise indicated.